Mark Sweep GC
日本語では「印掃式ゴミ集め」とかって言うらしい
スライド
概要
世界初のGC
John McCarthy, 1960
間接的GC
追跡型のGC
2つのPhaseからなる
Mark Phase
生きているオブジェクト全てにマークを付ける
この走査のことをのことを追跡(tracing)と呼ぶ
1. まず最初にルートから辿れるオブジェクトにマークを付ける
2. さらにそこから辿れるオブジェクトにマークを付けていく
生きているオブジェクトの数に比例してマークする時間がかかる
全てのオブジェクトを探索するので、試行回数自体は深さ優先探索でも幅優先探索でも同じだが、メモリの使用量の少ない前者がよく用いられる また、深さ優先探索を採用することで、「マーク→子を辿る」の一連の操作がキャッシュを利用しやすい
Sweep Phase
マークが付けられなかったオブジェクトを回収する
マーク済みのものものはこのフェーズでマークを外し、次のMark Phaseに備える
GCサイクルごとにマークの意味を反転するなら、全マークを外す時間を短縮できる
今回はマーク済み=生きている、だけど、次の回はマークなし=生きているのように
nextフィールドの話よくわからん?
ヒープ領域のサイズに比例した時間がかかる
First-fitの戦略を取る
メリット
実装が簡単
保守的GCとの相性が良い
ミューテータの読み出し、書き出し操作に全くオーバーヘッドがかからない
マークフェーズのスループットが高い
ビットを立てるだけ。
ヒープの空間的使用量の効率が良い
オブジェクトヘッダの余っているビットをマークビットに使用するぐらい
デメリット
フラグメンテーションが起こりがち
アロケートのたびにフリーリストを探索するので時間がかかる
コピーオンライトとの相性が悪い
Mark Phaseで、生きているオブジェクト全てにマークを「付ける」ので、「forkはしたけどコピーされていないもの」を書き換えることになり、そこでコピーされてしまう。
このせいで本来は発生しなかったコピーが頻発してしまいメモリを圧迫する
デメリットに対する対策
Multiple free-list
チャンクのサイズごとにフリーリストを用意する
フリーリストを全部探索する必要がなくなる
2ワード用、3ワード用、...、100ワード用、..、101ワード以上用の100個用意するのも割と現実的らしい
Big Bag Of Pages(BiBOP法)
Bitmap Marking
白本p.29-あんまり読めてない
マーキングの有無を各オブジェクトのヘッダではなく、別の場所にある2次元のテーブルで管理する
SweepPhaseのマークを外す処理を高速に行える
Lazy Sweep
Sweep Phaseにかかる時間がヒープサイズに比例して大きくなる問題への対策
スイープ操作によるミューテータの最大停止時間を減少させるための手法
GCによる全体の停止時間を減らしているわけではなく、そのコストを分割して返済している
Sweep Phaseでのスイープ操作を一括で行うのではなく、遅延させる
つまりMarkPhaseのあとにSweepPhaseを行わず、ミューテータに実行権を返す
ミューテータが新たにメモリを必要としたら、空きがあるかを探す
なければそこで部分的に(例えばMultiple free-listのブロックごとに)Sweepをして要求されたサイズのフリーリストを用意する
アロケート時に必要なチャンクが見つかるまでスイープ操作を行う
アロケータがスイープをする
キャッシュ効率も良い
Rubyでは1.9.3から導入された
ヘッダに格納するもの
マークの有無を表すフラグ
ヘッダもしくはヒープの外に用意してある表に格納
そのオブジェクトのサイズ
ビットマップマーキング
オブジェクトをマークしたかどうかの情報をビットマップマーキングを用いて記録する方法
オブジェクトとは別の場所(フリービットマップ)に各オブジェクトがマークされたかどうかの情報を記録する
これはコピーオンライトに対処するため
Ruby1.9以前では、オブジェクト内に記録していたので、マークフェーズでGCはRubyの共有されているメモリのほとんどに書き込みをお項なうことになってしまっていたので、コピーオンライトの最適化が無効化されていた
Mark Sweep GCが用いられている言語
jsも
concurrent Mark Sweep
関連ありそうなもの(未読
Rust実装